Linear-time algorithms.md (1134B)
1 +++ 2 title = "Linear-time algorithms" 3 +++ 4 5 # Linear-time algorithms 6 7 run faster than O(nlogn), but require special assumptions about input 8 9 ## Counting sort 10 11 - assume input is in fixed range {0…k} 12 - count number of occurrences of each: from 0 to k 13 - time complexity in ϴ(n+k) for length n 14 - k may absorb n and vice versa 15 - drawbacks: fixed range, requires space for array of length n 16 17 ## Radix sort 18 19 - assume input is in fixed range of integers 20 - sorting numbers considered as tuples 21 - consider from least significant digit, sorting lexicographically 22 - if counting is used, time complexity ϴ(d(n+k)) with d being dimension 23 24 ## Bucket sort 25 26 - assumes for correctness: keys in [0,1) 27 - assumes for time complexity: key uniform distribute over [0,1) 28 - has to be randomly uniformly distributed 29 - algorithm: 30 - for n elements, make array of n empty buckets 31 - for every array element a[i], insert a[i] into bucket[n*a[i]] 32 - sort each bucket using insertion sort 33 - concatenate all sorted buckets 34 - worst case: insertionSort is O(n²), so ϴ(n²) 35 - average case: ϴ(n) 36 - to improve worst case, don’t use insertion sort